Computational results for a stopping rule problem on averages

Suppose x₁, x₂, … are independently distributed random variables with Pr (x_i = 1) = Pr(x_i = ?1) = 1/2, and let s_n =

     

A model for manpower productivity during organization growth

A mathematical model is developed that enables organization and manpower planners to quantify the inefficiencies involved in rapid buildups of organizations, such as is frequently found in the aerospace industry shortly after the award of a major contract. Consideration is given to the time required to train, indoctrinate, and familiarize new workers with their jobs and the general program aspects. Once trained, workers are assumed to be productive. If the ratio of untrained to trained workers exceeds a critical value, called the buildup threshold, then the performance of the trained workers is degraded to the extent that they are no longer 100 percent efficient until this ratio returns to a value less than the threshold. The model is sufficiently general to consider an arbitrary manpower plan with more than one peak or valley. The model outputs are functions of real time and consist of the fraction of the total labor force which is productive, the fraction of the total labor units expended for nonproductive effort, the cumulative labor costs for productive effort, and the cumulative labor cost for all effort.     

A heuristic with tie breaking for certain 0–1 integer programming models

A heuristic for 0–1 integer programming is proposed that features a specific rule for breaking ties that occur when attempting to determine a variable to set to 1 during a given iteration. It is tested on a large number of small- to moderate-sized randomly generated generalized set-packing models. Solutions are compared to those obtained using an existing well-regarded heuristic and to solutions to the linear programming relaxations. Results indicate that the proposed heuristic outperforms the existing heuristic except for models in which the number of constraints is large relative to the number of variables. In this case, it performs on par with the existing heuristic. Results also indicate that use of a specific rule for tie breaking can be very effective, especially for low-density models in which the number of variables is large relative to the number of constraints.     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

An exact analysis of a joint production‐inventory problem in two‐echelon inventory systems

We consider a two‐echelon inventory system with a manufacturer operating from a warehouse supplying multiple distribution centers (DCs) that satisfy the demand originating from multiple sources. The manufacturer has a finite production capacity and production times are stochastic. Demand from each source follows an independent Poisson process. We assume that the transportation times between the warehouse and DCs may be positive which may require keeping inventory at both the warehouse and DCs. Inventory in both echelons is managed using the base‐stock policy. Each demand source can procure the product from one or more DCs, each incurring a different fulfilment cost. The objective is to determine the optimal base‐stock levels at the warehouse and DCs as well as the assignment of the demand sources to the DCs so that the sum of inventory holding, backlog, and transportation costs is minimized. We obtain a simple equation for finding the optimal base‐stock level at each DC and an upper bound for the optimal base‐stock level at the warehouse. We demonstrate several managerial insights including that the demand from each source is optimally fulfilled entirely from a single distribution center, and as the system's utilization approaches 1, the optimal base‐stock level increases in the transportation time at a rate equal to the demand rate arriving at the DC. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Inventory management with advance capacity information

An important aspect of supply chain management is dealing with demand and supply uncertainty. The uncertainty of future supply can be reduced if a company is able to obtain advance capacity information (ACI) about future supply/production capacity availability from its supplier. We address a periodic‐review inventory system under stochastic demand and stochastic limited supply, for which ACI is available. We show that the optimal ordering policy is a state‐dependent base‐stock policy characterized by a base‐stock level that is a function of ACI. We establish a link with inventory models that use advance demand information (ADI) by developing a capacitated inventory system with ADI, and we show that equivalence can only be set under a very specific and restrictive assumption, implying that ADI insights will not necessarily hold in the ACI environment. Our numerical results reveal several managerial insights. In particular, we show that ACI is most beneficial when there is sufficient flexibility to react to anticipated demand and supply capacity mismatches. Further, most of the benefits can be achieved with only limited future visibility. We also show that the system parameters affecting the value of ACI interact in a complex way and therefore need to be considered in an integrated manner. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

On optimality of one‐bug‐look‐ahead policies for a software testing model

The optimality of the One‐Bug‐Look‐Ahead (OLA) software release policy proposed by Morali and Soyer ( 15 ) is re‐examined in this paper. A counterexample is constructed to show that OLA is not optimal in general. The optimal stopping approach is then called upon to prove that OLA possesses weaker sense of optimality under conditional monotonicity and the strong sense of optimality holds under a more restrictive sample‐wise monotonicity condition. The NTDS data are analyzed for illustration, and OLA is shown to be robust with respect to model parameters. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Simulation of nonhomogeneous poisson processes by thinning

A simple and relatively efficient method for simulating one-dimensional and two-dimensional nonhomogeneous Poisson processes is presented The method is applicable for any rate function and is based on controlled deletion of points in a Poisson process whose rate function dominates the given rate function In its simplest implementation, the method obviates the need for numerical integration of the rate function, for ordering of points, and for generation of Poisson variates.     

Duality for quasi-concave programs with application to economics

A duality theory is developed for mathematical programs with strictly quasi-concave objective functions to be maximized over a convex set. This work broadens the duality theory of Rockafellar and Peterson from concave (convex) functions to quasi-concave (quasi-convex) functions. The theory is closely related to the utility theory in economics. An example from economic planning is examined and the solution to the dual program is shown to have the properties normally associated with market prices.